home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 3 / Cream of the Crop 3.iso / c_lang / strpp31.zip / REGEXP.CPP < prev    next >
C/C++ Source or Header  |  1994-04-18  |  16KB  |  670 lines
  1. /* -------------------------------------------------------------------- */
  2. /* String++ Version 3.10                                       04/13/94 */
  3. /*                                                                      */
  4. /* Enhanced string class for Turbo C++/Borland C++.                     */
  5. /* Copyright 1991-1994 by Carl W. Moreland                              */
  6. /*                                                                      */
  7. /* Derived from code Copyright 1988, Jim Mischel.  All rights reserved. */
  8. /*                                                                      */
  9. /* regexp.cpp                                                           */
  10. /* -------------------------------------------------------------------- */
  11.  
  12. #ifndef __STDDEF_H
  13. #include <stddef.h>
  14. #endif
  15.  
  16. #include "regexp.h"
  17.  
  18. #define    _RE_TRUE_    -1
  19. #define    _RE_FALSE_     0
  20. #define _RE_ALMOST_     1    // returned when a closure matches a NULL
  21.  
  22. const char ENDSTR    = '\0';
  23. const char EOL        = '$';
  24. const char BOL        = '^';
  25. const char NEGATE    = '^';
  26. const char CCL        = '[';
  27. const char NCCL        = ']';
  28. const char CCLEND    = ']';
  29. const char ANY        = '.';
  30. const char DASH        = '-';
  31. const char OR        = '|';
  32. const char ESCAPE    = '\\';
  33. const char LPAREN    = '(';
  34. const char RPAREN    = ')';
  35. const char CLOSURE    = '*';
  36. const char POS_CLO    = '+';
  37. const char ZERO_ONE    = '?';
  38. const char LITCHAR    = 'c';
  39. const char END_TERM    = 'e';
  40. const StrPP FS_DEFAULT    = "[ \t]+";
  41.  
  42. int    RSTART;            // start of matched substring
  43. int    RLENGTH;            // length of matched substring
  44. int    NF;            // number of fields from most current split
  45. RegExp FS(FS_DEFAULT);        // global field separator
  46.  
  47. /* -------------------------------------------------------------------- */
  48.  
  49. RegExp::RegExp(const StrPP& s)
  50. {
  51.   reExpression = s;
  52.  
  53.   if(reExpression() != "")
  54.     MakePattern();
  55. }
  56.  
  57. void RegExp::operator=(const char* p)
  58. {
  59.   reExpression = p;
  60.  
  61.   if(reExpression() != "")
  62.     MakePattern();
  63. }
  64.  
  65. void RegExp::operator=(const StrPP& s)
  66. {
  67.   reExpression = s;
  68.  
  69.   if(reExpression() != "")
  70.     MakePattern();
  71. }
  72.  
  73. /* -------------------------------------------------------------------- */
  74.  
  75. // MakePattern() - "compile" the regular expression into rePattern
  76.  
  77. const char* RegExp::MakePattern(void)
  78. {
  79.   static StrPP tmp;
  80.  
  81.   if(ParseExpression(tmp) == "" || reExpression != ENDSTR)
  82.   {
  83.     rePattern = "";
  84.     reExpression.Reset();
  85.     return NULL;
  86.   }
  87.   rePattern = tmp;
  88.   reExpression.Reset();
  89.   return rePattern;
  90. }
  91.  
  92. // ParseExpression() - Parse and translate an expression. Returns a pointer
  93. // to the compiled expression, or NULL on error.
  94.  
  95. const char* RegExp::ParseExpression(StrPP& expr)
  96. {
  97.   StrPP term;
  98.   expr = "";
  99.  
  100.   if(ParseTerm(term) == "")        // get the first term
  101.     return(NULL);
  102.  
  103.   while(reExpression == OR)        // parse all subsequent terms
  104.   {
  105.     expr += OR;
  106.     expr += term;
  107.     expr += END_TERM;
  108.     reExpression++;
  109.  
  110.     if(ParseTerm(term) == "")
  111.       return (NULL);
  112.   }
  113.   expr += term;
  114.   expr += END_TERM;
  115.  
  116.   return expr;
  117. }
  118.  
  119. // ParseTerm() - parse and translate a term.  Returns a pointer to the
  120. // compiled term or NULL on error.
  121.  
  122. const char* RegExp::ParseTerm(StrPP& term)
  123. {
  124.   StrPP factor;
  125.   term = "";
  126.  
  127.   if(reExpression == BOL)
  128.   {
  129.     term += reExpression[0];
  130.     reExpression++;
  131.   }
  132.   do
  133.   {
  134.     if(ParseFactor(factor) == "")
  135.       return(NULL);
  136.  
  137.     term += factor;
  138.   }
  139.   while(IsFactor());            // parse all factors of this term
  140.  
  141.   return term;
  142. }
  143.  
  144. // IsFactor() - returns _RE_TRUE_ for a valid factor character
  145.  
  146. int RegExp::IsFactor(void)
  147. {
  148.   static char* nfac_chars = "^|)]+?*";
  149.  
  150.   return (strchr(nfac_chars, reExpression[0]) == NULL) ? _RE_TRUE_ : _RE_FALSE_;
  151. }
  152.  
  153. // ParseFactor() - parse and translate a factor.  Returns a pointer to the
  154. // compiled factor or NULL on error.
  155.  
  156. const char* RegExp::ParseFactor(StrPP& factor)
  157. {
  158.   StrPP tmp;
  159.   factor = "";
  160.  
  161.   switch(reExpression[0])
  162.   {
  163.     case LPAREN:            // ( - parenthesised expression
  164.       reExpression++;
  165.       ParseExpression(tmp);
  166.       factor += tmp;
  167.       if(reExpression != RPAREN)
  168.     return(NULL);
  169.       reExpression++;
  170.       break;
  171.  
  172.     case CCL:                // [ - character class; Ex: [0-9]
  173.       reExpression++;
  174.       ParseCCL(tmp);
  175.       factor += tmp;
  176.       if(reExpression != CCLEND)
  177.         return(NULL);
  178.       reExpression++;
  179.       break;
  180.  
  181.     case ANY:                // .
  182.     case EOL:                // $
  183.       factor += reExpression[0];
  184.       reExpression++;
  185.       break;
  186.  
  187.     case ESCAPE    :            // \
  188.       reExpression++;
  189.       factor += LITCHAR;
  190.       factor += ParseEscape();
  191.       reExpression++;
  192.       break;
  193.  
  194.     case CLOSURE:            // *
  195.     case POS_CLO:            // +
  196.     case ZERO_ONE:            // ?
  197.     case NEGATE:            // ^
  198.     case CCLEND:            // ]
  199.     case RPAREN:            // )
  200.     case OR:                // |
  201.       return(NULL);            // not valid characters
  202.  
  203.     default:                // literal character
  204.       factor += LITCHAR;
  205.       factor += reExpression[0];
  206.       reExpression++;
  207.       break;
  208.   }
  209.  
  210.   if(reExpression == CLOSURE  ||    // check for closure
  211.      reExpression == ZERO_ONE ||
  212.      reExpression == POS_CLO)
  213.   {
  214.     if(ParseClosure(factor) == _RE_FALSE_)
  215.       return(NULL);
  216.   }
  217.   return factor;
  218. }
  219.  
  220. // ParseEscape() - returns ASCII value of character(s) following ESCAPE
  221.  
  222. char RegExp::ParseEscape(void)
  223. {
  224.   static char ch;
  225.  
  226.   switch(reExpression[0])
  227.   {
  228.     case 'b': reExpression++; return ('\b');    // backspace
  229.     case 't': reExpression++; return ('\t');    // tab
  230.     case 'f': reExpression++; return ('\f');    // formfeed
  231.     case 'n': reExpression++; return ('\n');    // linefeed
  232.     case 'r': reExpression++; return ('\r');    // carriage return
  233.  
  234.     case '0':                // 0-7 is octal constant
  235.     case '1':
  236.     case '2':
  237.     case '3':
  238.     case '4':
  239.     case '5':
  240.     case '6':
  241.     case '7':
  242.     {
  243.       ch = reExpression[0] - '0';
  244.       reExpression++;
  245.       if(reExpression >= '0' && reExpression < '8')
  246.       {
  247.         ch <<= 3;
  248.         ch += reExpression[0] - '0';
  249.         reExpression++;
  250.       }
  251.       if(reExpression >= '0' && reExpression < '8')
  252.       {
  253.         ch <<= 3;
  254.         ch += reExpression[0] - '0';
  255.         reExpression++;
  256.       }
  257.       return(ch);
  258.     }
  259.     default:                // otherwise, just that char
  260.       return(reExpression[0]);
  261.   }
  262. }
  263.  
  264. // ParseClosure() - place closure character and size before the factor
  265. // in the compiled string.
  266.  
  267. int RegExp::ParseClosure(StrPP& factor)
  268. {
  269.   if(factor.Len() > 253)
  270.     return _RE_FALSE_;            // closure expression too large
  271.  
  272.   factor.Insert(0, "  ");
  273.   factor[0] = reExpression[0];
  274.   factor[1] = (char)(factor.Len()-2);
  275.  
  276.   reExpression++;
  277.  
  278.   return _RE_TRUE_;
  279. }
  280.  
  281. // ParseCCL() - parse and translate a character class. Return pointer to the
  282. // compiled class or NULL on error.
  283.  
  284. const char* RegExp::ParseCCL(StrPP& ccl)
  285. {
  286.   int first = _RE_TRUE_;
  287.   int len;
  288.  
  289.   ccl = "[ ";
  290.  
  291.   if(reExpression == NEGATE)        // if first character is NEGATE (^)
  292.   {
  293.     ccl[0] = NCCL;            // then we have a negated
  294.     reExpression++;            // character class
  295.   }
  296.  
  297.   // parse all characters up to the closing bracket or end of string marker
  298.  
  299.   while(reExpression != CCLEND && reExpression != ENDSTR)
  300.   {
  301.     if(reExpression == DASH && first == _RE_FALSE_)    // DASH, check for range
  302.     {
  303.       reExpression++;
  304.       if(reExpression == NCCL)
  305.         ccl += DASH;            // not range, literal DASH
  306.       else
  307.       {
  308.         ParseDASH(ccl, reExpression);
  309.         reExpression++;
  310.       }
  311.     }
  312.     else
  313.     {
  314.       if(reExpression == ESCAPE)
  315.       {
  316.         reExpression++;
  317.         ccl += ParseEscape();
  318.         reExpression++;
  319.       }
  320.       else
  321.       {
  322.         ccl += reExpression[0];
  323.     reExpression++;
  324.       }
  325.     }
  326.     first = _RE_FALSE_;
  327.   }
  328.  
  329.   len = ccl.Len()-2;
  330.  
  331.   if(len > 255)
  332.     return NULL;            // character class too large
  333.   else
  334.   {
  335.     ccl[1] = (char)len;            // store CCL length at ccl[1]
  336.     return ccl;
  337.   }
  338. }
  339.  
  340. // ParseDASH() - fill in range characters.
  341.  
  342. const char* RegExp::ParseDASH(StrPP& ccl, char ch)
  343. {
  344.   static char c;
  345.  
  346.   for(c = ccl[ccl.Len() - 1] + 1; c <= ch; c++)
  347.     ccl += c;
  348.  
  349.   return ccl;
  350. }
  351.  
  352. /* -------------------------------------------------------------------- */
  353.  
  354. // Match() - Return the position of the first character of the left-most
  355. // longest substring of s that Matches pattern, or NULL if no match is
  356. // found. Sets RSTART and RLENGTH.
  357.  
  358. int RegExp::Match(const char* s, const char* pattern)
  359. {
  360.   char* c = (char*)s;
  361.   reLastChar = (char*)s;
  362.  
  363.   while(*c != ENDSTR)
  364.   {
  365.     if(MatchTerm(int(c-(char*)s), c, (char*)pattern) != _RE_FALSE_)
  366.     {
  367.       RSTART  = int(c-(char*)s);
  368.       RLENGTH = int(reLastChar - c);
  369.       return RSTART;
  370.     }
  371.     c++;
  372.   }
  373.   RSTART = RLENGTH = 0;
  374.   return -1;
  375. }
  376.  
  377. // MatchTerm() - Match a compiled term. Returns _RE_TRUE_, _RE_FALSE_,
  378. // or _RE_ALMOST_.
  379.  
  380. int RegExp::MatchTerm(int offset, char* s, char* pattern)
  381. {
  382.   reLastChar = s;
  383.  
  384.   if(*pattern == ENDSTR)
  385.     return _RE_FALSE_;
  386.  
  387.   do
  388.   {
  389.     switch(*pattern)
  390.     {
  391.       case BOL:                // ^ - match beginning of line
  392.         if(offset != 0)
  393.           return _RE_FALSE_;
  394.         pattern++;
  395.         break;
  396.  
  397.       case LITCHAR:            // c - match literal character
  398.         if(*s++ != *++pattern)
  399.           return _RE_FALSE_;
  400.         pattern++;
  401.         break;
  402.  
  403.       case END_TERM:            // e - skip end-of-term character
  404.         pattern++;
  405.         break;
  406.  
  407.       case ANY:                // . - match any character
  408.         if(*s++ == ENDSTR)        //     except end of string
  409.           return _RE_FALSE_;
  410.         pattern++;
  411.         break;
  412.  
  413.       case OR:
  414.         return MatchOR(offset, s, pattern);
  415.  
  416.       case CCL:                // [ - character class
  417.       case NCCL:            // ]
  418.         if(*s == ENDSTR)
  419.           return _RE_FALSE_;
  420.         if(!MatchCCL(*s++, pattern++))
  421.           return _RE_FALSE_;
  422.         pattern += pattern[0] + 1;
  423.         break;
  424.  
  425.       case EOL:                // $ - match end of string
  426.         if(*s != ENDSTR)
  427.           return _RE_FALSE_;
  428.         pattern++;
  429.         break;
  430.  
  431.       case ZERO_ONE:            // ?
  432.         return Match_0_1(offset, s, pattern);
  433.  
  434.       case CLOSURE:            // *
  435.       case POS_CLO:            // +
  436.       {
  437.         char ClosurePattern[1024];
  438.  
  439.         strncpy(ClosurePattern, pattern+2, *(pattern+1));
  440.         ClosurePattern[*(pattern+1)] = ENDSTR;
  441.         return MatchClosure(offset, s, pattern, ClosurePattern);
  442.       }
  443.  
  444.       default:
  445.  
  446.       // If we get to this point, then something has gone very wrong.
  447.       // Most likely, someone has tried to match with an invalid
  448.       // compiled pattern.
  449.  
  450.         return _RE_FALSE_;
  451.     }
  452.     reLastChar = s;
  453.   } while(*pattern != ENDSTR);
  454.  
  455.   return _RE_TRUE_;
  456. }
  457.  
  458. // MatchOR() - Handles selection processing.
  459.  
  460. int RegExp::MatchOR(int offset, char* s, char* pattern)
  461. {
  462.   char tmp_pattern[1024];
  463.   char *t1, *t2, *junk;
  464.  
  465.   // The first case is build into tmp_pattern. Second case is already there.
  466.   // Both patterns are searched to determine the longest matched substring.
  467.  
  468.   tmp_pattern[0] = ENDSTR;
  469.   pattern++;
  470.   junk = (char*)SkipTerm(pattern);
  471.  
  472.   strncat(tmp_pattern, pattern, int(junk-pattern));
  473.   strcat(tmp_pattern, SkipTerm(junk));
  474.   t1 = (MatchTerm(offset, s, tmp_pattern) != _RE_FALSE_) ? reLastChar : NULL;
  475.  
  476.   // The second pattern need not be searched if the first pattern results
  477.   // in a match through to the end of the string, since the longest possible
  478.   // match has already been found.
  479.  
  480.   if(t1 == NULL || *reLastChar != ENDSTR)
  481.   {
  482.     t2 = (MatchTerm(offset, s, junk) != _RE_FALSE_) ? reLastChar : NULL;
  483.  
  484.     // determine which matched the longest substring
  485.  
  486.     if(t1 != NULL && (t2 == NULL || t1 > t2))
  487.       reLastChar = t1;
  488.   }
  489.   return (t1 == NULL && t2 == NULL) ? _RE_FALSE_ : _RE_TRUE_;
  490. }
  491.  
  492. // SkipTerm() - Skip over the current term and return a pointer to the
  493. // next term in the pattern.
  494.  
  495. const char* RegExp::SkipTerm(char* pattern)
  496. {
  497.   register int nterm = 1;
  498.  
  499.   while(nterm > 0)
  500.   {
  501.     switch(*pattern)
  502.     {
  503.       case OR:
  504.         nterm++;
  505.         break;
  506.  
  507.       case CCL:
  508.       case NCCL:
  509.       case CLOSURE:
  510.       case ZERO_ONE:
  511.       case POS_CLO:
  512.         pattern++;
  513.         pattern += pattern[0];
  514.         break;
  515.  
  516.       case END_TERM:
  517.         nterm--;
  518.         break;
  519.  
  520.       case LITCHAR:
  521.         pattern++;
  522.         break;
  523.     }
  524.     pattern++;
  525.   }
  526.   return pattern;
  527. }
  528.  
  529. // Match_0_1() - Match the ZERO_ONE operator. First, this routine attempts
  530. // to match the entire pattern with the input string. If that fails, it
  531. // skips over the closure pattern and attempts to match the rest of the
  532. // pattern.
  533.  
  534. int RegExp::Match_0_1(int offset, char* s, char* pattern)
  535. {
  536.   char* old_s = s;
  537.  
  538.   if(MatchTerm(offset, s, pattern+2) == _RE_TRUE_)
  539.     return _RE_TRUE_;
  540.   else if(MatchTerm(offset, old_s, pattern+2+*(pattern+1)) == _RE_FALSE_)
  541.     return _RE_FALSE_;
  542.   else
  543.     return _RE_ALMOST_;
  544. }
  545.  
  546. // MatchClosure() - Match CLOSURE and POS_CLO. Match as many of the
  547. // closure patterns as possible, then attempt to match the remaining
  548. // pattern with what's left of the input string. Backtrack until we've
  549. // either matched the remaing pattern or we arrive back at where we
  550. // started.
  551.  
  552. int RegExp::MatchClosure(int offset, char* s,
  553.                          char* pattern, char* ClosurePattern)
  554. {
  555.   char* old_s = s;
  556.  
  557.   if(MatchTerm(offset, s, ClosurePattern) == _RE_TRUE_)
  558.   {
  559.     old_s = reLastChar;
  560.     if(MatchClosure(offset, old_s, pattern, ClosurePattern) != _RE_FALSE_)
  561.       return _RE_TRUE_;
  562.     else
  563.       return MatchTerm(offset, old_s, pattern+2+*(pattern+1));
  564.   }
  565.   else if(*pattern != CLOSURE)      // POS_CLO requires at least one match
  566.     return _RE_FALSE_;
  567.   else if(MatchTerm(offset, old_s, pattern+2+*(pattern+1)) == _RE_TRUE_)
  568.     return _RE_ALMOST_;
  569.   else
  570.     return _RE_FALSE_;
  571. }
  572.  
  573. // MatchCCL() - Match a character class or negated character class
  574.  
  575. int RegExp::MatchCCL(char c, char* pattern)
  576. {
  577.   register int x;
  578.   char ccl = *pattern++;
  579.  
  580.   for(x = *pattern; x > 0; x--)
  581.   {
  582.     if(c == pattern[x])
  583.       return(ccl == CCL);
  584.   }
  585.   return(ccl != CCL);
  586. }
  587.  
  588. /* -------------------------------------------------------------------- */
  589.  
  590. // Return the position of the first instance of t in s, or -1 if no match.
  591.  
  592. int index(const StrPP& s, const RegExp& t)
  593. {
  594.   return match(s, (RegExp)t);
  595. }
  596.  
  597. // sub() - Substitute 'to' for the leftmost longest substring of str
  598. // matched by the regular expression 'from'. Return number of substitutions
  599. // made.
  600.  
  601. int sub(const RegExp& from, const StrPP& to, StrPP& str)
  602. {
  603.   if(match(str, (RegExp&)from) == -1)
  604.     return 0;
  605.  
  606.   str.Replace(RSTART, RLENGTH, to);
  607.   return 1;
  608. }
  609.  
  610. // gsub() - Substitute 'to' globally for all substrings in str matched by
  611. // the regular expression 'from'. Return number of substitutions made.
  612.  
  613. int gsub(const RegExp& from, const StrPP& to, StrPP& str, int count)
  614. {
  615.   int n = 0;
  616.   ParseString tmp = str;
  617.  
  618.   while(match(tmp, (RegExp&)from) != -1)
  619.   {
  620.     tmp.Replace(RSTART, RLENGTH, to);
  621.     tmp += RSTART+RLENGTH;
  622.     if(++n == count)
  623.       break;
  624.   }
  625.   tmp.Reset();
  626.   str = tmp;
  627.  
  628.   return n;
  629. }
  630.  
  631. // split() - Split the string s into fields in the array a on field
  632. // separator fs. Returns number of fields.  Also sets the global variable
  633. // NF.
  634.  
  635. int split(const StrPP& s, StrPP*& array, const RegExp& fs)
  636. {
  637.   StrPP *tmp;
  638.   ParseString ps = s;
  639.   int rstart  = RSTART;            // save RSTART and RLENGTH
  640.   int rlength = RLENGTH;
  641.   NF = 1;
  642.  
  643.   while(match(ps, (RegExp)fs) != -1)
  644.   {
  645.     ps += RSTART+RLENGTH;
  646.     NF++;
  647.   }
  648.  
  649.   tmp = new StrPP[NF];
  650.   ps.Reset();
  651.   NF = 0;
  652.  
  653.   while(match(ps, (RegExp)fs) != -1)
  654.   {
  655.     tmp[NF++] = ps(0, RSTART);
  656.     ps += RSTART+RLENGTH;
  657.   }
  658.   array = tmp;
  659.  
  660.   RSTART  = rstart;            // restore globals
  661.   RLENGTH = rlength;
  662.   return (NF);
  663. }
  664.  
  665. ostream& operator<<(ostream& strm, const RegExp& re)
  666. {
  667.   return strm << re.reExpression();
  668. }
  669.  
  670.